package game.pathfinding;

import game.Tile;
import game.TileMap;

import java.util.Vector;

import util.Util;

public class AStar extends Pathfinder {
	private class StarPoint
	{
		protected PathElement elem = new PathElement();
		protected Vector<StarPoint> whiteList = new Vector<StarPoint>();
		protected float dist = 0.0f;
		protected boolean generated = false;
		
		public void generateList(TileMap m, int tx, int ty, StarPoint last)
		{
			check(m, elem.X - 1, elem.Y, tx, ty, last);
			check(m, elem.X + 1, elem.Y, tx, ty, last);
			check(m, elem.X, elem.Y - 1, tx, ty, last);
			check(m, elem.X, elem.Y + 1, tx, ty, last);
			
			if(Pathfinder.DIAGONALS)
			{
				check(m, elem.X - 1, elem.Y - 1, tx, ty, last);
				check(m, elem.X - 1, elem.Y + 1, tx, ty, last);
				check(m, elem.X + 1, elem.Y - 1, tx, ty, last);
				check(m, elem.X + 1, elem.Y + 1, tx, ty, last);
			}
			
			generated = true;
		}
		
		private void check(TileMap m, int x, int y, int tx, int ty, StarPoint last)
		{
			Tile t = m.getTileAt(x, y);
			if(t == null) { if(Pathfinder.DEBUG_MODE) System.out.println("# No tile at " + x + ", " + y); return; }
			if(t.isObstacle()) { if(Pathfinder.DEBUG_MODE) System.out.println("# Obstacle at " + x + ", " + y); return; }
			if(m.getCharacterAt(x, y) != null) { if(Pathfinder.DEBUG_MODE) System.out.println("# Character at " + x + ", " + y); return; }
			
			StarPoint sp = new StarPoint();
			sp.setCoords(x, y);
			if(sp.equals(last)) { if(Pathfinder.DEBUG_MODE) System.out.println("# Same as last : " + x + ", " + y); return; }
			sp.dist = Util.getDistF(x, y, tx, ty) + m.getTileAt(x, y).getMovPenalty() * 0.5f;
			whiteList.add(sp);
		}
		
		public void setCoords(int x, int y)
		{
			elem.X = x;
			elem.Y = y;
		}
		
		public String toString()
		{
			String r = "Pos : " + elem.X + ", " + elem.Y + "\n";
			for(StarPoint p : whiteList)
				r += "    " + p.toString() + "\n";
			return r;
		}
		
		public StarPoint findBest()
		{
			if(Pathfinder.DEBUG_MODE) System.out.println("Candidates : " + whiteList.size());
			if(whiteList.size() == 0) return null;
			
			StarPoint min = whiteList.get(0);
			for(int i = 1; i < whiteList.size(); ++i)
				if(whiteList.get(i).dist < min.dist)
					min = whiteList.get(i);
			
			return min;
		}
		
		public void blackList(StarPoint p)
		{
			for(int i = 0; i < whiteList.size(); ++i)
			{
				if(whiteList.get(i).equals(p))
				{
					whiteList.remove(i);
					i--;
				}
			}
		}
		
		public boolean equals(StarPoint sp)
		{
			if(sp == null) return false;
			return elem.X == sp.elem.X && elem.Y == sp.elem.Y;
		}
		
		public boolean equals(int x, int y)
		{
			return elem.X == x && elem.Y == y;
		}
		
		public boolean adjecentTo(StarPoint sp)
		{
			return adjecentTo(sp.elem.X, sp.elem.Y);
		}
		
		public boolean adjecentTo(int x, int y)
		{
			int dX = Math.abs(x - elem.X);
			int dY = Math.abs(y - elem.Y);
			
			if(Pathfinder.DIAGONALS)
			{
				return (dX + dY) <= 2 && dX <= 1 && dY <= 1;
			}
			else
			{
				return (dX + dY) <= 1;
			}
		}
	}
	
	private static final int MAX_ITERATIONS = 500;
	
	@Override
	public Path findPath(TileMap map, int sX, int sY, int tX, int tY, int budget) {
		Vector<StarPoint> stack = new Vector<AStar.StarPoint>();
		
		if(Pathfinder.DEBUG_MODE) System.out.println("START : " + sX + ", " + sY + ";   TARGET : " + tX + ", " + tY);
		
		StarPoint p = new StarPoint();
		p.setCoords(sX, sY);
		p.generateList(map, tX, tY, null);
		stack.add(p);
		
		int iters = 0;
		while(stack.size() > 0)
		{
			iters++;
			if(iters >= MAX_ITERATIONS)
			{
				Path path = new Path();
				path.found = false;
				path.totalCost = 0;
				return path;
			}
			
			StarPoint cp = stack.lastElement();
			StarPoint np = cp.findBest();
			
			if(np == null) 
			{ 
				stack.remove(cp);
				if(stack.size() > 0)
				{
					stack.lastElement().blackList(cp);
					if(Pathfinder.DEBUG_MODE) System.out.println("Backtracking...");
					continue;
				}
				else
				{
					if(Pathfinder.DEBUG_MODE) System.out.println("Path not found!");
					break;
				}
			}
			
			stack.add(np);
			if(Pathfinder.DEBUG_MODE) System.out.println("Advancing to " + np);
			if(np.equals(tX, tY))
			{
				if(Pathfinder.DEBUG_MODE) System.out.println("PATH FOUND! Steps : " + (stack.size() - 1));
				break;
			}
			
			if(!stack.lastElement().generated) stack.lastElement().generateList(map, tX, tY, cp);
		}
		
		if(stack.size() > 0)
		{
			optimize(stack);
			
			Path path = new Path();
			int cost = 0;
			for(int i = 1; i < stack.size(); ++i)
			{
				StarPoint sp = stack.get(i);
				PathElement pe = sp.elem;
				cost += map.getTileAt(pe.X, pe.Y).getMovPenalty();
				pe.fits = cost <= budget;
				if(pe.fits) path.lastFit = pe;
				path.stops.add(pe);
			}
			path.found = true;
			path.totalCost = cost;
			return path;
		}
		else
		{
			Path path = new Path();
			path.found = false;
			path.totalCost = 0;
			return path;
		}
	}

	private void optimize(Vector<StarPoint> stack)
	{
		Vector<StarPoint> temp = new Vector<AStar.StarPoint>();
		temp.addAll(stack);
		stack.clear();
		
		stack.add(temp.get(0));
		stack.add(temp.get(1));
		
		for(int i = 1; i < temp.size(); i++)
		{
			StarPoint elem = temp.get(i);
			int skipEl = i;
			for(int j = i + 1; j < temp.size(); ++j)
			{
				if(temp.get(j).adjecentTo(temp.get(i)))
				{
					skipEl = j;
					elem = temp.get(j);
				}
			}
			
			if(i != skipEl)
				i = skipEl - 1;
			stack.add(elem);
		}
		stack.remove(stack.lastElement());
	}
}
